\input macros
\def\bookline{\CLOS\  Specification}
\def\chapline{Basic User Interface Concepts}

\beginChapter 1.{Common Lisp Object System Specification}%
{Basic User Interface Concepts}{Basic User Interface Concepts}

Contributors to this document include Daniel G. Bobrow, Linda G.
DeMichiel,\break Richard P. Gabriel, Kenneth Kahn, Sonya E. Keene,
Gregor Kiczales, Larry\break Masinter, David A. Moon, Mark Stefik, and
Daniel L. Weinreb.

Comments and suggestions on this document are encouraged.
Changes will be incorporated over the next several months.
This text will be made available to the X3J13 Committee for the
Common Lisp Standards effort.

\endTitlePage

\beginSection{Introduction}

This proposal presents a description of the standard user
interface for object-oriented programming in the \CLOS.  A second
document, ``The \CLOS\ Meta-Object Protocol'' describes how the
\CLOS\ can be customized to accommodate existing object-oriented
paradigms and to define new ones.

Under this proposal, the primitive entities of Common Lisp are called
{\bit objects}.  The fundamental objects of the \CLOS\ are
classes, generic function objects, and method objects.  [What is
the ontological status of method combination?]  [Meta-objects?]

A {\bit class\/} object determines the structure and behavior of a set
of other objects, called its {\bit instances}.  The class of an object
indirectly determines the set of operations into which the object can
enter.  It is an important feature of the \OS\ that every Common Lisp
data structure is an object that is an {\bit instance\/} of a unique
class.

{\bit Generic functions} are objects that may be specialized to
provide class-specific operations.  A generic function is a function
that is able to designate one of a set of possible operations based on
the classes of its arguments.  A generic function can be used as an
argument to {\bf funcall} and {\bf apply} and stored in the
symbol-function cell of a symbol.

The class-specific operations provided by generic functions are
themselves defined and implemented by {\bit methods}.  A method is
also a function object.  The method object contains a method function
and a set of {\bit argument specializers\/} that specify when the
given method is applicable.

%  A method can be used as an argument to
%  {\bf funcall} and {\bf apply} and stored in the symbol-function cell
%  of a symbol.  [This needs to be decided.]

When a generic function is invoked, the selection and sequencing of
the individual methods that are applicable may be further controlled by the
{\bit method combination\/} facility.   Method combination qualifiers,
types, and rules [or what do we call these?] can be used to precisely
define which methods are invoked when a given generic function is called
with specific classes of arguments.

\vfill
\endSection%{Introduction}


\beginSection{Classes}

A {\bit class\/} is an object that determines the structure and behavior
of a set of other objects, called its {\bit instances}.

Like other objects, all classes are themselves instances of other classes.
The class of the class of an object is termed the {\bit metaclass\/} of that
object.  Less formally, we will also use the term {\bit metaclass\/} to
refer to a class that has instances that are themselves classes.
The metaclass determines the form of inheritance used by its classes and
the representation of the instances of those classes.

A class can inherit properties directly or indirectly from one or more
other classes.  A class that is defined so as to inherit from another
class is said to {\bit include\/} that class.  A class that inherits
from a class is said to be a {\bit subclass\/} of that inherited
class.  A class from which another class inherits properties is called
a {\bit superclass\/} of the inheriting class.  The inheritance
relationship is transitive.

Classes are organized into a {\bit lattice}.  There is a mapping from
the Common Lisp type lattice into the Common Lisp Object System class
lattice.  All of the standard Common Lisp types specified in 
{\it Common Lisp: The Language\/} by Guy L. Steele Jr. except {\bf atom}
and {\bf common} have a corresponding class.

The \OS\ includes a set of standard objects.  We use the term 
{\bit standard object\/} to refer to any object whose metaclass is
{\bf class}.  The class {\bf object} specifies the default behavior of the
set of all objects whose metaclass is {\bf class}.  In other words,
all standard objects inherit (directly or indirectly) from the class
{\bf object}.

The \OS\ also defines a set of standard classes.  A {\bit standard
class\/} is any class that is an instance of the class {\bf class}.
The class {\bf class} is itself of class {\bf class}.  It is therefore
both a standard class and a standard object.  The class {\bf object}
is also a standard class since it is also an instance of the class
{\bf class}.  As a standard object, the class {\bf class} is a
subclass of the class {\bf object}.

\vfill\eject
\Vskip 1pc!
\boxfig
{\bf\tabskip 0pt plus 1fil
\halign to \hsize{&#\hfil\cr
array&hashtable&sequence\cr
atom*&integer&short-float\cr
bignum&keyword&simple-array\cr
bit&list&simple-bit-vector\cr
bit-vector&long-float&simple-string\cr
character&nil&simple-vector\cr
common*&null&single-float\cr
compiled-function&number&standard-char\cr
complex&package&stream\cr
cons&pathname&string\cr
double-float&random-state&string-char\cr
fixnum&ratio&symbol\cr
float&rational&t\cr
function&readtable&vector\cr
}}
\caption{Standard Common Lisp types.  All these types except atom and common have\break
a corresponding class.}
\endfig



\beginsubSection{Defining Classes}

Classes with metaclass {\bf class} (standard classes)
are defined with the macro {\bf defclass}.
The use and definition of classes with other metaclasses %are
will be
discussed in the chapter ``Meta-Object Protocol.''

The syntax for {\bf defclass} is given in Figure~1-3.

The new class created by {\bf defclass} is a subclass of all the
classes specified in the {\it includes\/} list of the {\bf defclass}
form.  A class that is defined in this way is the most specific
element of a sublattice from which descriptions are inherited.  The
order of the classes in the {\it includes\/} list determines a local
precedence for classes and for the selection of methods.  The
transitive closure of all the {\it includes\/} specifies all the
classes that this class inherits from.  An ordering of this list for
purposes of precedence is called the {\bit class precedence list}.

The class precedence list for a standard class is computed as follows:

[To be spec'd.]
%1. A list is created, starting with the given class, of all the classes
%encountered in a depth-first traversal of
%the classes in the {\it includes\/} list of that class.  The classes in
%the {\it includes\/} list are processed in left-to-right order (the order
%of local precedence).
%
%2. If more than one occurrence of a class appears in the list that
%results from step 1, only the last occurrence of that class is kept.
%
%3. It is verified that the list that results from step 2 preserves the
%local precedence indicated in the {\it includes\/} list of each class
%encountered.  If any such local precedence is violated, an error is
%signalled.
\endsubSection

\beginsubSection{The Structure of Class Objects}

\endsubSection%{The Structure of Class Objects}

\beginsubSection{Creating Instances of Classes}

\endsubSection%{Creating Instances of Classes}

\beginsubSection{Superclasses}

\endsubSection%{Superclasses}

\beginsubSection{Inheritance}

\endsubSection%{Inheritance}

\beginsubSection{Class Precedence}

%brief introduction to notion of class precedence
\endsubSection%{Class Precedence}

\beginsubSection{Accessing Slots}

Slots can be accessed in two ways: by use of the accessors defined in
the {\bf defclass} form and by use of the primitive function
{\bf slot-value}.

The function {\bf slot-value} can be used with any of the slot names
specified in the {\bf defclass} form to access a specific slot in an object
of the given class.  If the object has no such slot, an error is
signalled.

The automatically-generated accessors specified in the {\bf defclass} form
are implemented in terms of {\bf slot-value}.

\endsubSection

\beginsubSection{Types and Classes}

The \OS\  maps the Common Lisp type space into the space
of classes.  
Figure~1-2 displays part of the lattice of classes that are instances of
a subclass of {\bf standard-type-class}.

Creating a type by means of {\bf defstruct} also creates a class in
this lattice.  Such a class is an instance of {\bf structure-class}
and an immediate subclass of the class that
corresponds to the type given as its
{\bf :includes} argument.  If no such type was specified, it
is an immediate subclass of the class {\bf t}.

The following precedence relations hold among classes:
{\bf list} has precedence over {\bf symbol} (for {\bf nil});
{\bf array} has precedence over {\bf sequence} (for vectors);
{\bf vector} has precedence over {\bf simple-array} (for simple-vectors);
{\bf bit-vector} has precedence over {\bf simple-array} (for simple-bit-vectors);
and {\bf string} has precedence over {\bf simple-array} (for simple-strings).

The classes {\bf number}, {\bf integer}, {\bf rational}, {\bf float},
{\bf list}, and {\bf sequence} are {\bit abstract classes}, that is,
they can never be directly instantiated.  The function {\bf class-of}
will never return one of these classes.

\endsubSection%{Integrating Types and Classes}

\eject
\beginsubSection{Lattice of classes that are instances of standard-type-class}
\fig{
\def\IgnoreLineBreaks{\catcode'15=9     \catcode'12=9}
\def\IgnoreWhiteSpace{\catcode'11=9 \catcode'40=9 \IgnoreLineBreaks}
\def\DontIgnoreWhiteSpace{\catcode'12=\active\catcode'15=5\catcode'11=10\catcode'40=10}

\font \pipefont= circlew10
\font \foofont = cmr10 at 1sp

\IgnoreWhiteSpace

\let \adv=\advance
\def\he{height}
\def\wi{width}
\def\de{depth}

\newdimen \stroke       
\stroke= \fontdimen8\pipefont   % thickness of line in circles
\newdimen \radius       \radius=6pt     % radius of circles

\newdimen\irad \irad=\radius\advance\irad by -.5\stroke
\newdimen\orad \orad=\radius\advance\irad by  .5\stroke

\newbox\BStrutbox

\setbox\BStrutbox\hbox{\vrule\wi0pt\he8.5pt\de8.5pt}
\def\BoxStrut{\unhcopy\BStrutbox}

% Arrows

\newdimen\ArrowShift
\ArrowShift=\fontdimen22\tensy
\advance\ArrowShift by -0.5\stroke

\def\StrikeOut #1
{       \setbox0\hbox{#1}
        \hbox to 1\wd0
        {       \vrule \he\stroke\de0pt\wi\wd0
                \hskip-\wd0
                \unhbox0
        }
}

\def\LeftArrow
{       \hskip 0.5\stroke
        \StrikeOut{\lower\ArrowShift\hbox to 10pt{\tensy\char'40\hss}}
}

\def\RightArrow
{       \StrikeOut{\lower\ArrowShift\hbox to 10pt{\hss\tensy\char'41}}
        \hskip 0.5\stroke
}

\def\ArrowLine
{       \StrikeOut{\hskip 10pt\hskip 0.5\stroke}
}

\def\LeftToRight
{       \let\RightSideArrow=\ArrowLine
        \let\LeftSideArrow=\RightArrow
}

\def\RightToLeft
{       \let\LeftSideArrow=\ArrowLine
        \let\RightSideArrow=\LeftArrow
}

\def\NoArrows
{       \let\LeftSideArrow=\ArrowLine
        \let\RightSideArrow=\ArrowLine
}
% boxes around tokens

\let\NonterminalFont=\tenrm

\newbox\TStrutbox
\setbox0\hbox{\NonterminalFont{Bg}}
\setbox\TStrutbox\hbox{\vrule\wi0pt\he\ht0\de\dp0}
\def\TextStrut{\unhcopy\TStrutbox}

\def\HorzLine{\hrule \he \stroke \de 0pt}
\def\HFil{\leaders\HorzLine\hfil}
\def\HFill{\leaders\HorzLine\hfill}

\def\Nonterminal#1
{\setbox1\vbox to 0pt{
        \vss
        \hbox{\TextStrut\NonterminalFont\space#1\space\hskip-\stroke}
        \vss}
        \hbox{
        \BoxStrut
        \LeftSideArrow
        \lower\irad\vbox{
                \TopSquare
                \copy1
                \BotSquare}
        \RightSideArrow}
}

\def\TopSquare
{       \hbox{
        \vrule\he\stroke\de\irad\wi\stroke
        \vrule\he\stroke\de0pt\wi\wd1
        \vrule\he\stroke\de\irad\wi\stroke}
}

\def\BotSquare
{       \hbox{
        \vrule\he\orad\de0pt\wi\stroke
        \vrule\he\stroke\de0pt\wi\wd1
        \vrule\he\orad\de0pt\wi\stroke}
}

\def\\#1{\Nonterminal{#1}\HFil}
\def\last#1{{\def\RightSideArrow{}\Nonterminal{#1}}}

% piping

\def\foo{\rlap{\foofont\char'40}}
\def\foo{}

\def\FulVert{\vrule             \wi\stroke\foo\hskip-\stroke}
\def\TopVert{\vrule\de-\irad    \wi\stroke\foo\hskip-\stroke}
\def\BotVert{\vrule\he-\orad    \wi\stroke\foo\hskip-\stroke}

\def\Center#1,#2.
{\hskip\radius\foo#1\lower.5\stroke\hbox{\pipefont#2}\hskip\radius}

\def\ru{\char'10\hskip -2\radius}
\def\rd{\char'11\hskip -2\radius}
\def\ld{\char'12\hskip -2\radius}
\def\lu{\char'13\hskip -2\radius}
\def\thru{\hskip-\radius\vrule\he\stroke\de0pt\wi2\radius\hskip\radius\hskip-2\radius}

\def\Center#1,#2.
{\foo\hskip\radius#1{\pipefont#2\unskip}\hskip-\radius}

\def\LT{\Center\BotVert,\lu.}
\def\LU{\Center\FulVert,\lu.}
\def\LL{\Center\FulVert,\ld.}
\def\LB{\Center\TopVert,\ld.}
\def\LMid{\Center\TopVert\BotVert,\rd\ru\thru.}
\def\LMU{\Center\TopVert,\rd\thru.}
\def\LML{\Center\BotVert,\ru\thru.}
\def\LFD{\Center\FulVert,\ru\thru.}
\def\LS{\Center\TopVert\BotVert,\rd\ru.}

\def\RT{\Center\BotVert,\ru.}
\def\RU{\Center\FulVert,\ru.}
\def\RL{\Center\FulVert,\rd.}
\def\RB{\Center\TopVert,\rd.}
\def\RMid{\Center\TopVert\BotVert,\ld\lu\thru.}
\def\RMU{\Center\TopVert,\ld\thru.}
\def\RML{\Center\BotVert,\lu\thru.}

\def\Cross{\Center\FulVert,\thru.}
\def\LR{\Center,\thru.}
\def\TB{\Center\FulVert,.}
%  ShiftBox

\newbox\x
\newbox\y
\newbox\tempy
\newbox\z
\newbox\tempz

\def\ShiftBox#1{
\savemod
\saverulebox
\setbox\x
\vbox{  \everycr{\noalign{{\modifyrulebox\global\setbox\z\hbox{}}}}
        \halign{&\setbox\x\hbox{##}
        \global \setbox\z\hbox{\unhbox\z\vrule\he\ht\x\de\dp\x\wi0pt}
                \unhbox\x
                \cr
                #1}}%
\lower\ht\y\box\x\HFil
\restoremod
\restorerulebox
}

\def\saverulebox{
        \setbox\tempy\box\y
\global \setbox\y\vbox{}
        \setbox\tempz\box\z
\global \setbox\z\hbox{}
}

\def\restorerulebox{
\global \setbox\y\box\tempy
\global \setbox\z\box\tempz
}

\def\topmod{}

\def\thisrow{\global\let\modifyrulebox\firstmod}

\def\firstmod{
        \global\setbox\y\vbox{\hrule\he0pt\wi0pt\de\dp\z}
        \global\let\modifyrulebox\latermod
}
\def\latermod{
        \global\setbox\y\vbox{\unvbox\y\hrule\he\ht\z\de\dp\z\wi0pt}
}
\def\savemod{
        \let\tempmod\modifyrulebox
\global \let\modifyrulebox\topmod
}
\def\restoremod{
\global\let\modifyrulebox\tempmod
}

\DontIgnoreWhiteSpace
{\baselineskip0pt
\lineskip0pt
\LeftToRight
\IgnoreWhiteSpace

\def\ms{\os\os\os\os}
\def\os{\omit\span}
\hbox{
\\{NIL}
\ShiftBox{
    \ms\LT\\{bit}&\RT\cr
    \ms\ShiftBox{
        \ShiftBox{
            \ShiftBox{
                \LU\\{fixnum}&\RT\cr
                \LU\\{bignum}&\RMU\thisrow\cr
                }\\{integer}&\RML\thisrow\cr
            \LU\\{ratio}&\RB\cr
            }\\{rational}&\RT\cr
        \ShiftBox{
            \LU\\{short-float}&\RT\cr
            \LU\\{single-float}&\RMid\thisrow\cr
            \LU\\{double-float}&\RL\cr
            \LU\\{long-float}&\RB\cr
            }\\{float}&\RMid\thisrow\cr
        \LU\\{complex}&\RB\cr
        }\\{number}&\RU\cr
    \ms\LU\\{standard-char}\\{string-char}\\{character}&\RU\cr
    \LU\\{keyword}&\os\os\os\RML\\{symbol}&\RU\cr
    \LU\\{null}&\os\os\os\LS&\TB\cr
    \LMid\\{cons}&\os\os\RMU\\{list}&\RML\\{sequence}&\RMid\thisrow\cr
    \os\LL\\{simple-vector}&\LML\HFil&\RML\\{vector}&\LS&\TB\cr
    \os\LL\\{simple-bit-vector}&\LFD\\{bit-vector}&\RL&\TB&\TB\cr
    \os\LL\\{simple-string}&\LFD\\{string}&\RB&\TB&\TB\cr
    \os\TB&\os\LB\HFil\\{simple-array}&\RMU\\{array}&\RL\cr
    \ms\LL\\{stream}&\RL\cr
    \ms\LL\\{hash-table}&\RL\cr
    \ms\LL\\{readtable}&\RL\cr
    \ms\LL\\{package}&\RL\cr
    \ms\LL\\{pathname}&\RL\cr
    \ms\LL\\{function}&\RL\cr
    \ms\LL\\{compiled-function}&\RL\cr
    \ms\LB\\{random-state}&\RB\cr
}
\last{T}}}
\hbox{}
}\caption{This figure shows all required subclass relationships among the classes that\break
are instances of
standard-type-class, with the exception of classes defined by means of\break
defstruct.  Implementations may choose to impose additional ones.}
\endfig

\endsubSection%{Types and Classes}

\endSection%{Classes}


\beginSection{Generic Functions and Methods}

\beginsubSection{Introduction to Generic Functions}

Like ordinary Lisp functions, generic functions take arguments, perform
an operation, and perhaps return useful values.  An ordinary function
has a single body of code that is always executed when the function is
called.  The implementation of a generic function varies from call to
call, depending on the class of one or more of the arguments.  An
argument that selects which method or methods to run is called a
specialized argument.  A generic function can have several methods
associated with it, and the class of each specialized argument to the
generic function indicates which method or methods to use.  The generic
function is said to discriminate on the classes of its arguments.

Ordinary functions and generic functions are called with identical
syntax:

  (function-name arguments...)
 
Generic functions are not only syntactically compatible with ordinary
functions; they are semantically compatible as well:

 o They are true functions that can be passed as arguments and used as
   the first argument to FUNCALL and APPLY.   

 o The name of a generic function is in a certain package and can be
   exported if it is part of an external interface.  This allows
   programmers to keep unrelated programs separate.  

Ordinary functions have a single definition; generic functions have a
distributed definition.   The definition of a generic function can be
found in a DEFGENERIC form and a set of DEFMETHOD forms.    A DEFGENERIC
form provides information about the contract of the generic function.
Evaluating these forms produces a generic-function object,
which can be FUNCALL'ed.   Typically a generic-function object is stored
as the function definition of the symbol that is the name of the generic
function.

When a new DEFGENERIC form is evaluated and the generic function of this
name already exists (that is, the function definition of the first
subform of DEFGENERIC is a generic-function object), the existing
generic-function object is modified.   Evaluating a DEFGENERIC does not
modify any of the methods associated with the generic function.

\endsubSection%{Introduction to Generic Functions}

\beginsubSection{Introduction to Methods}

A DEFMETHOD form contains the code that is to be run when the
specialized arguments to the generic function cause this method to be
selected.   DEFMETHOD creates a method-object.  If a DEFMETHOD form is 
evaluated and the method-object already exists, the new definition 
replaces the old.

Each method has a "specialized" lambda list, which indicates 
which of its arguments are to be used for method selection.  Only
required parameters can be specialized.  [It is still under discussion
whether optional parameters can be specialized.]  A specialized
parameter is a list of (variable-name parameter-specializer), where
parameter-specializer is one of:

   o A user-defined class
   o (QUOTE object)
   o A symbol naming a built-in class corresponding to one of these CL
     types:  

        array               integer          rational
        bit-vector          list             readtable
        character           long-float       sequence
        compiled-function   null             short-float
        complex             number           single-float
        cons                package          string
        double-float        pathname         symbol
        float               random-state     t
        hash-table          ratio            vector
 
Note that a parameter-specializer is a symbol, and cannot be a list
such as (vector single-float).  

Methods can also have arguments not intended to be used for selection;
such parameters are in normal DEFUN syntax.

A method that has only one specialized parameter is called a classical
method.   A method with more than one specialized parameter is a
multi-method.   A method with no specialized parameters is a default
method; it is always available for the generic function, but often
shadowed by a more specific method.   A default method can also have a 
parameter specializer of T; this is the same as if that parameter had no 
specializer.  An individual method is one whose specialized parameter 
is (QUOTE object); this method is selected if the corresponding 
argument to the generic function is EQL to the object.   The parameter
specializer (QUOTE object) is more specific than any other specializer. 
 
Methods can have qualifiers.   If a method has no qualifier it is called
a primary method.   Some examples of method qualifiers are:  :BEFORE,
:AFTER, and :AROUND.   A :BEFORE method specifies code that runs before
the primary method, and an :AFTER method specifies code that runs after
the primary method.  Method qualifiers give the method combination
procedure a way to distinguish between methods.  

\endsubSection%{Introduction to Methods}

\beginsubSection{Congruent Lambda-lists for all Methods of a Generic Function}

The lambda-list in the DEFGENERIC specifies the "shape" of the generic  
function arguments.  All methods for this generic function must be
congruent with this shape; this implies that the system can determine 
whether a call is syntactically correct.   The rules are: 

[The following is a first approximation of these rules, which need
to be discussed further:]

1.  Each method must have the same number of required arguments. 

2.  Each method must have the same number of \&optional arguments, but 
    methods can supply different defaults for \&optional arguments. 

3.  If \&allow-other-keys is used by one method, all methods must use
    it.   

4.  If \&allow-other-keys is not used, each method must allow the same
    number of \&key arguments, and these keyword arguments must have
    the same names across methods.  

5.  If \&rest is used by one method, all methods must use it. 

6.  The use of \&aux need not be consistent across methods.  

The method receives the same arguments that the generic function 
received. 

\endsubSection%{Congruent Lambda-lists for all Methods of a Generic Function}


\endSection%{Generic Functions and Methods}

\beginSection{Method Selection and Combination}

When a generic function is called, it must decide: 

 o  Which method (or methods) to call
 o  The order in which to call the methods
 o  Which value (or values) to return 
 o  If CALL-NEXT-METHOD is used, it is important to know which is the
    "next" method to call. 

These requirements are handled by the following 4-step procedure: 

1.  Select the set of available methods. 

Given a generic function and the arguments to it, the set of available
methods includes all methods for that generic function whose specialized
parameters match their corresponding arguments.     A method's
specialized parameter matches its corresponding argument if:

    o The class of the argument has the class of the specializer as a 
      component class.   

    o Or, the specialized parameter is (QUOTE object) and the argument
      is EQL to the object. 

2.  Sort the available methods into a precedence order. 

To compare the precedence of two methods, examine their parameter
specializers in order from left to right.  (Note that the left to right
precedence order is the default. It can be changed by the
:ARGUMENT-PRECEDENCE-ORDER option to DEFGENERIC.)  Compare each argument
to the generic function to the corresponding parameter specializers of
the methods. 

The first pair of parameter specializers that are not equal determine
the precedence.  Method X is more specific than method Y if method X's
parameter specializer appears earlier than method Y's parameter specializer
in the class precedence list of the class of the argument.  (Due to the
way the set of available methods is chosen, it is guaranteed that 
the parameter specializers are present in the class precedence list of
the class of the argument.) 

Any unspecialized parameters have an implied type specifier of T.  T is
implied at the very end of each class precedence list, so it is less
specific than any other class.  (QUOTE object) is more specific than any
class.  (If both parameter specializers are quoted objects, they must be
equal or both methods would not be available for this argument.)

The resulting list of available methods is sorted with the most specific
method first and the least specific method at the end.

3.  Apply method combination to the sorted list of methods. 

The method combination technique specified for the generic function receives
the sorted list of available methods and returns a Lisp form.  This form
contains calls to some or all of the methods, and defines the value(s)
to be  returned by the generic function.   The method combination might 
make some of the methods reachable via CALL-NEXT-METHOD, rather than
calling them directly.   

The meaning of the qualifiers of a method is defined entirely by this
step of the procedure.  Method qualifiers give the method combination 
procedure a way to distinguish between methods.   

See "DAEMON Method Combination" for a description of how the default
method combination chooses methods to call, makes some methods available
by CALL-NEXT-METHOD, and defines the values to be returned by the
generic function. 

The DEFINE-METHOD-COMBINATION facility allows the programmer to
customize this step of the procedure without needing to consider what 
happens in the other steps.   (The other steps of the procedure can be
customized using meta-objects.)

4.  Consider the resulting Lisp form.

In the simplest implementation, the generic function simply evaluates
the form.  In practice, this is too inefficient and most implementations
do not execute this entire procedure every time a generic function is
called.  Instead they employ a variety of optimizations such as 
precomputation into tables, compilation, and/or caching to speed things
up.  Some illustrative examples (not exhaustive):

  o Use a hash table keyed by the class of the arguments.
  o Compile the Lisp form and save the resulting compiled-function.
  o Recognize the Lisp form as an instance of a pattern of control structure
    and substitute a closure of a function that implements that structure.

The Lisp form serves as a more general interface.  For example, a tool that
determines which methods are called and presents them to the user works by
going through the above procedure and then analyzing the form to determine
which methods it calls, instead of evaluating it.


\endSection%{Method Selection and Combination}

\beginSection{DAEMON Method Combination}

The default type of method combination is called :DAEMON.  A method's
type is determined by the qualifier arguments to DEFMETHOD.  The 
following method types are recognized by :DAEMON method combination:

primary  These methods have no qualifiers in the DEFMETHOD form.   They
         are the most common type of method.   CALL-NEXT-METHOD may
         be used in a primary method.  

:BEFORE :BEFORE methods have the keyword :BEFORE as their only DEFMETHOD 
        qualifier argument.  They are used to specify code that is to
        run before the primary method. 

:AFTER  :AFTER methods have the keyword :AFTER as their only DEFMETHOD
        qualifier argument.  They are used to specify code that is to
        run after the primary method. 

:AROUND :AROUND methods have the keyword :AROUND as their only 
        DEFMETHOD qualifier argument.  Inside 
        the body of an :AROUND method, the function CALL-NEXT-METHOD can
        be used to immediately call the "next method" (see below). 
        When the next method returns, the :AROUND method can execute
        more code, perhaps based on the returned value(s).   

The semantics of :DAEMON method combination are:

  o If there are any :AROUND methods, the most specific :AROUND
    method is executed, and supplies the value(s) of the generic
    function.  

  o If an :AROUND method uses CALL-NEXT-METHOD, the next most
    specific :AROUND method is executed, if one is available.  

    If there are no :AROUND methods at all, or if CALL-NEXT-METHOD 
    is done by the least specific :AROUND method, the other methods are 
    executed in the following way: 

       o All the :BEFORE methods are executed, in most-specific-first
         order. 

       o The most specific primary method is executed, and supplies the
         value(s) returned by the generic function (or by
         CALL-NEXT-METHOD in the lease specific :AROUND method). 
         If it does CALL-NEXT-METHOD, 
         the second most specific primary method is executed, and so on
         until there are no more primary methods.   An error is
         signalled if CALL-NEXT-METHOD is used and there is no primary
         method available to call. 

       o All the :AFTER methods are executed in most-specific-last order.

Special Notes:

In :DAEMON combination, if there are any available methods at all, then 
there must be an available primary method or there is no method to
produce the value(s).   In such cases an error is signalled.

When all of the methods are primary methods:   If CALL-NEXT-METHOD
is not used, the classical method-shadowing behavior is obtained.  If
CALL-NEXT-METHOD is used, the effect is the same as RUN-SUPER in
LOOPS.  

It should be noted that all :AROUND methods run before any primary
methods run.  Thus a less specific :AROUND method runs before a more
specific primary method.   

This section has described the use of the default :DAEMON method
combination type, and the default order, which is :MOST-SPECIFIC-FIRST.
You can use the :METHOD-COMBINATION option to DEFGENERIC and supply an
argument of :MOST-SPECIFIC-LAST to change the order of methods.
:MOST-SPECIFIC-LAST reverses the order of the primary methods.  The
order of the :BEFORE, :AFTER, and :AROUND methods is not changed, and it
is still the case that all of the :AROUND methods are executed before
any primary methods.


\endSection%{DAEMON Method Combination}


\beginSection{Determining the Class Precedence List}

A class precedence list is used in several ways.  The method selection 
and combination process uses the class precedence list to order methods
from most specific to least specific.   When one class has several 
components, a more specific class can override options declared in the 
DEFCLASS form of a less specific class.    

\beginsubSection{Rules for Determining Class Precedence}

The DEFCLASS forms of a class and each of its super-classes set 
local constraints on the ordering of classes.  When a class is built
from super-classes, all of the local constraints of the class and its
super-classes are taken into account, and an ordering is computed that
satisfies all of these constraints.  In other words, the DEFCLASS
forms specify partial orderings, which must be merged into one total
ordering.

Three rules govern the ordering of classes:

1. A class always precedes its own super-classes.

2. The local ordering of super-classes within each DEFCLASS form is
preserved. 

3. Duplicate classes are eliminated from the ordering; if a class
appears more than once, it is placed as close to the beginning of the
ordering as possible, while still obeying the other rules.

\endsubSection%{Rules for Determining Class Precedence}

\beginsubSection{Constructing a Tree of Classes}

One way to merge the partial orderings is to construct a tree 
of classes.   The root of the tree is the class for which we are
computing a class precedence list.   From that root, the class's
super-classes are added from left to right, as they appear in the
DEFCLASS form.   

The ordering is determined by walking through the tree in depth-first
left-to-right order, and adding each class to the ordering if it fits
the constraints of the three rules.  If the class can be placed next in
the ordering without transgressing one of the three rules, it is added.
If adding it would transgress a rule, that class is skipped.  If the end
of the tree is reached and some classes have not yet been placed in the
ordered list, we walk through the tree again, continuing to apply the
three rules to the remaining classes and add them to the ordering.  In
complicated programs, it is conceivable that we could walk through the
tree several times.

If some classes cannot be ordered according to the rules, an error is 
signalled to inform the user of the conflicting constraints.   An
example of this is given at the end of this section. 

Here is an example of determining a class precedence list.
The classes are defined: 

(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit (food) ())
(defclass spice (food) ())
(defclass food () ())

The tree of classes for PIE is:


                 pie
                /   \
            apple  cinnamon
             /         \
          fruit      spice
            /           \
          food         food      


The list begins with PIE.  We continue, adding APPLE and 
FRUIT.   So far, the (incomplete) ordered list is: 

     (pie apple fruit 

The next class is FOOD, but we cannot place it next in the ordering
because doing so would transgress the rule that a class always precedes
its own super-classes.   If placed next, FOOD would precede SPICE,
and we know that SPICE must precede FOOD.    Thus we skip
FOOD and continue through the tree.    Because FOOD appears
later in the tree, we pick it up then.   The ordering is now complete:

     (pie apple fruit cinnamon spice food)

\endsubSection%{Constructing a Tree of Classes}

\beginsubSection{When Several Orderings are Possible}

In many cases, the three rules define a single valid ordering of
classes.    In other cases, several orderings are valid.  For example, 
suppose PIE class and its super-classes are defined as follows:

(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())

The tree-walk results in the ordering: 

     (pie apple fruit cinnamon spice) 

In fact, there are two additional valid orderings: 

     (pie apple cinnamon fruit spice) 
     (pie apple cinnamon spice fruit)

A well-conceived program must not depend on any one of those 
orderings, but should work equally well under any of them.   For 
example, if your program depends on SPICE preceding FRUIT in
the ordering for PIE, you should make that constraint explicit by 
including those two classes in the list of super-classes in the 
DEFCLASS form for PIE.

\endsubSection%{When Several Orderings are Possible}

\beginsubSection{Conflicting Class Definitions}

It is possible to write a set of class definitions that cannot be 
ordered using the rules.   For example: 

(defclass new-class (fruit apple) ())
(defclass apple (fruit) ())

FRUIT must precede APPLE because the local ordering of super-classes is
preserved.  APPLE must precede FRUIT because a class always precedes its
own super-classes.  When this situation occurs, an error is signalled
when the system tries to compute the class precedence list.  At that
point you can redefine one or more of the classes to resolve the
problem, presumably by changing the local order of super-classes to
resolve the conflict.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

(defclass pie (apple cinnamon) ())
(defclass pastry (cinnamon apple) ())

The ordering for PIE is:  (pie apple cinnamon)	

The ordering for PASTRY is:  (pastry cinnamon apple)

There is no problem with the fact that APPLE precedes CINNAMON in the
ordering of the super-classes of PIE, but not in the ordering for
PASTRY.    However, you cannot build a new class that has both PIE and
PASTRY as super-classes .

\endsubSection%{Conflicting Class Definitions}

\endSection%{Determining the Class Precedence List}

\beginSection{Declaration Method Combination}

We are currently working to integrate the programmatic ({\bf run-super})
and declarative ({\bf define-method-combination}) method combination
techniques.   This is still under discussion. 

\endSection%{Declarative Method Combination}


\beginSection{Meta Objects}

\beginsubSection{Metaclasses}

The {\bit metaclass\/} of an object is the class of its class.  The metaclass
determines the form of inheritance used by its classes and
the representation of the instances of its classes.  The metaclass mechanism
can be used to provide particular forms of optimization or to tailor
the \OS\  for particular uses (such as the implementation of other
object languages---like Flavors, Smalltalk-80, and Loops).

Any new metaclass must define the structure of its instances, how their storage
is allocated, how their slots are accessed, and how slots and methods are
inherited.  The protocol for defining
metaclasses will be discussed in the chapter ``Meta-Object Protocol.''
\endsubSection

\beginsubSection{Standard Metaclasses}

The \OS\  defines a number of {\bit standard metaclasses}.  These include
the following:
{\bf standard-type-class}, {\bf structure-class}, and {\bf class}.

The class {\bf standard-type-class} is a superclass of all the classes
that correspond to the standard Common Lisp types specified in
{\it Common Lisp: The Language\/} by Guy L. Steele Jr. except {\bf atom} and
{\bf common}.  These types are listed in Figure~1-1.
This metaclass allows the special kind of class
inheritance rules that are needed to handle the classes that 
correspond to the standard Common Lisp types.
It is not possible to make an instance
of a class whose class is {\bf standard-type-class} using the function
{\bf make-instance}.  
%It is possible to define methods for built-in classes.

The class {\bf structure-class} is a subclass of {\bf standard-type-class}.  
All classes defined by means of {\bf defstruct} are instances or
{\bf structure-class} or a subclass of {\bf structure-class}.
%The use of {\bf defstruct} implicitly defines a new class which is an
%instance of {\bf structure-class}.

%Instances of {\bf primitive-lisp-type-class} are classes that correspond
%to the basic Common Lisp types.  
%While all classes that correspond to the types
%listed in Figure}1-1 must be instances of either {\bf structure-class}
%or {\bf primitive-lisp-type-class}, no implementation is {\it required\/} to
%have any class that is an instance of {\bf primitive-lisp-type-class}.
\endsubSection

\endSection

%\beginSection{Meta-Objects}

%Includes objects for classes, objects for methods, objects for generic functions.

%Use: efficiency in implementation; experimentation.

%Allows for variations in the representation of objects, the syntax of
%methods, the combination of methods.

%Can be used to provide tuning and optimization for a particular application.

%\endSection

\endChapter
\bye